#include <iostream>

using namespace std;

template<class T>
struct AVLTreeNode
{
    explicit AVLTreeNode (const T &data = T ())
            : pLeft (nullptr), pRight (nullptr), pParent (nullptr), data (data), bf (0)
    {}
    
    AVLTreeNode<T> *pLeft;
    AVLTreeNode<T> *pRight;
    AVLTreeNode<T> *pParent;
    T              data;
    int            bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
    typedef AVLTreeNode<T> Node;
public:
    AVLTree ()
            : _pRoot (nullptr)
    {}
    
    bool Insert (const T &data)
    {
        // 先按照二叉搜索树的方式进行插入
        if (nullptr == _pRoot)
        {
            _pRoot = new Node (data);
            return true;
        }
        
        // 按照二叉搜索树特性：找待插入节点在树中的位置
        // 并保存其双亲
        Node *pCur    = _pRoot;
        Node *pParent = nullptr;
        while (pCur)
        {
            pParent = pCur;
            if (data < pCur->data)
            {
                pCur = pCur->pLeft;
            }
            else if (data > pCur->data)
            {
                pCur = pCur->pRight;
            }
            else
            {
                return false;
            }
        }
        
        // 插入新节点
        pCur          = new Node (data);
        if (data < pParent->data)
        {
            pParent->pLeft = pCur;
        }
        else
        {
            pParent->pRight = pCur;
        }
        pCur->pParent = pParent;
        
        while (pParent)
        {
            // 更新pParent的平衡因子
            if (pCur == pParent->pLeft)
            {
                pParent->bf--;
            }
            else
            {
                pParent->bf++;
            }
            
            if (0 == pParent->bf)
            {
                break;
            }
            else if (-1 == pParent->bf || 1 == pParent->bf)
            {
                pCur    = pParent;
                pParent = pCur->pParent;
            }
            else
            {
                // pParent->bf: 2 || -2
                // pParent的节点失去平衡
                if (2 == pParent->bf)
                {
                    // 右子树高-->最后必须左单旋
                    if (1 == pCur->bf)
                    {
                        RotateL (pParent);
                    }
                    else
                    {
                        RotateRL (pParent);
                    }
                }
                else
                {
                    if (-1 == pCur->bf)
                    {
                        RotateR (pParent);
                    }
                    else
                    {
                        RotateLR (pParent);
                    }
                }
                
                break;
            }
        }
        
        return true;
    }
    
    void InOrder ()
    {
        InOrder (_pRoot);
    }
    
    Node *LeftMost ()
    {
        if (nullptr == _pRoot)
        {
            return nullptr;
        }
        
        Node *pCur = _pRoot;
        while (pCur->pLeft)
        {
            pCur = pCur->pLeft;
        }
        
        return pCur;
    }
    
    Node *RightMost ()
    {
        if (nullptr == _pRoot)
        {
            return nullptr;
        }
        
        Node *pCur = _pRoot;
        while (pCur->pRight)
        {
            pCur = pCur->pRight;
        }
        
        return pCur;
    }
    
    bool IsAVLTree ()
    {
        return IsAVLTree (_pRoot);
    }

private:
    // 验证二叉搜索树是否为有效的
    bool IsAVLTree (Node *pRoot)
    {
        if (nullptr == pRoot)
        {
            return true;
        }
        
        int leftHeight  = Height (pRoot->pLeft);
        int rightHeight = Height (pRoot->pRight);
        
        if (abs (rightHeight - leftHeight) > 1 ||
            rightHeight - leftHeight != pRoot->bf)
        {
            return false;
        }
        
        return IsAVLTree (pRoot->pLeft) && IsAVLTree (pRoot->pRight);
    }
    
    size_t Height (Node *pRoot)
    {
        if (nullptr == pRoot)
        {
            return 0;
        }
        
        size_t leftHeight  = Height (pRoot->pLeft);
        size_t rightHeight = Height (pRoot->pRight);
        
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
    
    
    void RotateR (Node *pParent)
    {
        Node *pSubL  = pParent->pLeft;
        Node *pSubLR = pSubL->pRight;
        
        // 改变pParent和pSubL孩子的指向
        pParent->pLeft = pSubLR;
        if (pSubLR)
        {
            pSubLR->pParent = pParent;
        }
        
        pSubL->pRight = pParent;
        
        // 更新pParent和pSubL的双亲
        Node *pPParent = pParent->pParent;
        pParent->pParent = pSubL;
        pSubL->pParent   = pPParent;
        
        // 更新原pParent双亲的左||右指针域指向
        if (nullptr == pPParent)
        {
            _pRoot = pSubL;
        }
        else
        {
            if (pParent == pPParent->pLeft)
            {
                pPParent->pLeft = pSubL;
            }
            else
            {
                pPParent->pRight = pSubL;
            }
        }
        
        pParent->bf = pSubL->bf = 0;
    }
    
    void RotateL (Node *pParent)
    {
        Node *pSubR  = pParent->pRight;
        Node *pSubRL = pSubR->pLeft;
        
        pParent->pRight = pSubRL;
        if (pSubRL)
        {
            pSubRL->pParent = pParent;
        }
        
        pSubR->pLeft = pParent;
        Node *pPParent = pParent->pParent;
        pParent->pParent = pSubR;
        pSubR->pParent   = pPParent;
        
        if (nullptr == pPParent)
        {
            _pRoot = pSubR;
        }
        else
        {
            if (pParent == pPParent->pLeft)
            {
                pPParent->pLeft = pSubR;
            }
            else
            {
                pPParent->pRight = pSubR;
            }
        }
        
        pParent->bf = pSubR->bf = 0;
    }
    
    void RotateRL (Node *pParent)
    {
        Node *pSubR  = pParent->pRight;
        Node *pSubRL = pSubR->pLeft;
        int  bf      = pSubRL->bf;
        
        RotateR (pParent->pRight);
        RotateL (pParent);
        
        // 更新部分节点的平衡因子
        if (bf == -1)
        {
            pSubR->bf = 1;
        }
        else if (bf == 1)
        {
            pParent->bf = -1;
        }
    }
    
    void RotateLR (Node *pParent)
    {
        Node *pSubL  = pParent->pLeft;
        Node *pSubLR = pSubL->pRight;
        int  bf      = pSubLR->bf;
        
        RotateL (pParent->pLeft);
        RotateR (pParent);
        if (-1 == bf)
        {
            pParent->bf = 1;
        }
        else if (1 == bf)
        {
            pSubL->bf = -1;
        }
    }
    
    void InOrder (Node *pRoot)
    {
        if (pRoot)
        {
            InOrder (pRoot->pLeft);
            cout << pRoot->data << " ";
            InOrder (pRoot->pRight);
        }
    }

private:
    Node *_pRoot;
};


int main ()
{
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
